//
//  main.c
//  kuai快速排序sort
//
//  Created by Song on 2018/4/9.
//  Copyright © 2018年 Song. All rights reserved.
//

//  nlog2n

#include <stdio.h>

#define length 7

void quickSort(int arr[], int _left, int _right) {
    int left = _left;
    int right = _right;
    int temp = 0; // 基准元素
    
    if (left < right) { // 至少有两个待排元素
        
        temp = arr[left]; // 待排元素的第一个元素（最左边）作为基准元素
        
        while (left != right) { // 从左右两边交替扫描，直到 left = right
            while (right > left && arr[right] > temp) { // 从右往左扫描,找到比基准元素小的元素
                right --;
            }
            arr[left] = arr[right];
            
            while (left < right && arr[left] < temp) { //从左往右扫描，找到第一个比基准元素大的元素
                left ++;
            }
            arr[right] = arr[left];
        }
        
        arr[right] = temp; // 基准元素归位
        
        // 递归：
        quickSort(arr, _left, left - 1); // 基准元素左边的元素 递归
        quickSort(arr, right + 1, _right); // 基准元素右边的元素 递归
    }
}

int main(int argc, const char * argv[]) {
    
    int array[length] = {10,5,3,1,7,2,8};
    printf("排序前：");
    for (int a = 0; a<length; a++) {
        printf("%d ",array[a]);
    }
    
    quickSort(array, 0, length-1);
    
    printf("\n");
    
    printf("排序后：");
    for (int a = 0; a<length; a++) {
        printf("%d ",array[a]);
    }
    
    printf("\n");
    
    return 0;
}
